package com.yiwenup.sorting._08_couting;

import com.yiwenup.sorting.base.Sort;

/**
 * 计数排序：针对一定范围的整数排序
 **/
public class CountingSortV1 extends Sort<Integer> {
    @Override
    protected void work() {
        // 1. 找到最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        // 2.开辟内存空间
        int[] counts = new int[max + 1];

        // 3.统计每个元素出现的次数
        for (int i = 0; i < array.length; i++) {
            counts[array[i]]++;
        }

        // 4.遍历
        int index = 0;
        for (int i = 0; i < counts.length; i++) {
            while (counts[i--] > 0) {
                array[index++] = counts[i];
            }
        }
    }
}
